#include <iostream>
#include <vector>
using namespace std;

void swap(int&a,int&b)
{
    int tmp = a;
    a = b;
    b = tmp;
    
}

//三数取中
int GetMidi(vector<int>&a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
			return mid;
		else
		{
			if (a[left] > a[right])
				return right;
			else
				return left;
		}
	}
	else//left<=mid
	{
		if (a[mid] < a[right])
			return mid;
		else//mid>right
		{
			if (a[left] > a[right])//mid>left>right
				return left;
			else
				return right;
		}
	}
}


int calMid(vector<int>&v,int l,int r)
{
    int key = GetMidi(v,l,r);
    while(l<r)
    {
        while(l<r&&v[r]>v[key]) r-=1;
        while(l<r&&v[l]<v[key]) l+=1;
        swap(v[l],v[r]);
    }    
    swap(v[l],v[key]);
    return l;
}
int findKthSmallest(int input,vector<int>&v,int l,int r)
{
    if(l==r)
    {
        return v[l];
    }
    else
    {
        int mid = calMid(v,l,r);
        if(mid+1 == input) return v[mid];
        else if(mid+1>input)
        {
           return findKthSmallest(input,v,l,mid-1);
        }
        else
        {
            return findKthSmallest(input,v,mid+1,r);
        }
    }
}

int main()
{
    cout<<"input:"<<endl;
    int input = 0;
    cin>>input;
    int arr[] = {9,8,7,6,5,4,3,2,1,0};
    vector<int>v(arr,arr+10);
    int ret = findKthSmallest(input,v,0,v.size()-1);
    cout<<"KthSmallest:"<<ret<<endl;
    return 0;
}
